#include "parser.h"

#ifdef TEST_AST
#define PRIVATE
#else
#define PRIVATE static
#endif

#define CHECK_NODE(child, parent) \
    if (child == NULL) { \
        destroyAST(parent); \
        return NULL; \
    }

static char *colrefs[] = {
    "*",        /* all column */
    "user_id", "name", "email",
    "book_id", "quantity", "available", "category", "title", "author",
    "borrow_id", "borrow_date", "return_date", "status"
};

static char *tblrefs[] = {
    "user", "book", "borrow"
};

/* PRIVATE function declaration start */

PRIVATE ASTNode *createASTNode(const ASTNodeType type, const char *rule, const char *value);
PRIVATE void addChild(ASTNode *parent, ASTNode *child);

PRIVATE ASTNode *parseStmtInsert(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseStmtDelete(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseStmtSelect(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseStmtUpdate(const char *sql, int *index, int *last_index);

PRIVATE ASTNode *parseSelect(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseDelete();
PRIVATE ASTNode *parseInsert();
PRIVATE ASTNode *parseUpdate(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseFrom(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseJoin(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseWhere(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseInto(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseValues(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseSet(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseColumnList(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseTableList(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseRecordList(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseRecord(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseCondition(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseOr(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseAnd(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseExpr(const char *sql, int *index, int *last_index);
PRIVATE ASTNode *parseExprs(const char *sql, int *index, int *last_index);

PRIVATE int checkColref(const char *ref);
PRIVATE int checkTblref(const char *ref);

/* PRIVATE function declaration end */

void printAST(ASTNode *root, int level)
{
    if (root == NULL) return;

    for (int i = 0; i < level; i++)
        printf("  ");
    printf("%s: %s\n", root->rule, root->value);

    if (root->children != NULL) {
        for (int i = 0; i < root->child_count; i++) {
            printAST(root->children[i], level + 1);
        }
    }
}

void destroyAST(ASTNode *root)
{
    if (root == NULL) return;

    if (root->children != NULL) {
        for (int i = 0; i < root->child_count; i++) {
            destroyAST(root->children[i]);
        }
    }

    free(root);
    root = NULL;
}

ASTNode *parseSQL(const char *sql, int *index, int *last_index)
{
    Token token = getNextToken(sql, index, last_index);
    ASTNode *stmt_node;

    switch (token.type) {
        case TOKEN_SELECT:
            stmt_node = parseStmtSelect(sql, index, last_index);
            break;

        case TOKEN_DELETE:
            stmt_node = parseStmtDelete(sql, index, last_index);
            break;

        case TOKEN_UPDATE:
            stmt_node = parseStmtUpdate(sql, index, last_index);
            break;

        case TOKEN_INSERT:
            stmt_node = parseStmtInsert(sql, index, last_index);
            break;

        default:
            errMsg("ERROR: invalid statement\n");
            return NULL;
    }

    if (stmt_node == NULL) 
        return NULL;

    ASTNode *root = createASTNode(AST_SQL, "<SQL>", NULL);
    addChild(root, stmt_node);

    return root;
}


/* PRIVATE function implemention start */

PRIVATE ASTNode *createASTNode(const ASTNodeType type, const char *rule, const char *value)
{
    if (type == AST_UNKNOWN) {
        panic("SYSERR!");
    }

    if (rule == NULL) {
        panic("SYSERR!");
    }

    ASTNode *node = (ASTNode *) malloc(sizeof(ASTNode));
    if (node == NULL) {
        panic("SYSERR!");
    }

    node->type = type;

    strncpy(node->rule, rule, strlen(rule) + 1);

    if (value != NULL) {
        strncpy(node->value, value, strlen(value) + 1);
    } else {
        node->value[0] = '\0';
    }

    node->child_count = 0;
    for (int i = 0; i < MAX_AST_NODES; i++) {
        node->children[i] = NULL;
    }

    return node;
}

PRIVATE void addChild(ASTNode *parent, ASTNode *child)
{
    if (parent->child_count < MAX_AST_NODES) 
        parent->children[parent->child_count++] = child;
}

PRIVATE ASTNode *parseStmtSelect(const char *sql, int *index, int *last_index)
{
    Token token;

    ASTNode *stmt_select_node = createASTNode(AST_STMT_SELECT, "<STMT_SELECT>", NULL);

    /* select */
    ASTNode *select_node = parseSelect(sql, index, last_index);
    CHECK_NODE(select_node, stmt_select_node);
    addChild(stmt_select_node, select_node);

    /* from */
    token = getNextToken(sql, index, last_index);
    if (token.type != TOKEN_FROM) {
        errMsg("ERROR: expected 'from'.\n");
        destroyAST(stmt_select_node);
        return NULL;
    }
    ASTNode *from_node = parseFrom(sql, index, last_index);
    CHECK_NODE(from_node, stmt_select_node);
    addChild(stmt_select_node, from_node);

    /* join */
    token = getNextToken(sql, index, last_index);
    if (token.type != TOKEN_JOIN) {
        *index = *last_index;
    } else {
        ASTNode *join_node = parseJoin(sql, index, last_index);
        CHECK_NODE(join_node, stmt_select_node);
        addChild(stmt_select_node, join_node);
    }

    /* where */
    token = getNextToken(sql, index, last_index);
    if (token.type != TOKEN_WHERE) {
        *index = *last_index;
        return stmt_select_node;
    } else {
        ASTNode *where_node = parseWhere(sql, index, last_index);
        CHECK_NODE(where_node, stmt_select_node);
        addChild(stmt_select_node, where_node);
    }

    return stmt_select_node;
}

PRIVATE ASTNode *parseSelect(const char *sql, int *index, int *last_index)
{
    ASTNode *select_node = createASTNode(AST_CLAUSE_SELECT, "<SELECT>", "select");

    ASTNode *column_list_node = parseColumnList(sql, index, last_index);
    CHECK_NODE(column_list_node, select_node);
    addChild(select_node, column_list_node);

    return select_node;
}

PRIVATE ASTNode *parseFrom(const char *sql, int *index, int *last_index)
{
    ASTNode *from_node = createASTNode(AST_CLAUSE_FROM, "<FROM>", "from");

    ASTNode *table_list_node = parseTableList(sql, index, last_index);
    CHECK_NODE(table_list_node, from_node);
    addChild(from_node, table_list_node);

    return from_node;
}

PRIVATE ASTNode *parseWhere(const char *sql, int *index, int *last_index)
{
    ASTNode *where_node = createASTNode(AST_CLAUSE_WHERE, "<WHERE>", "where");

    ASTNode *condition_node = parseCondition(sql, index, last_index);
    CHECK_NODE(condition_node, where_node);
    addChild(where_node, condition_node);

    return where_node;
}

PRIVATE ASTNode *parseColumnList(const char *sql, int *index, int *last_index)
{
    ASTNode *column_list_node = createASTNode(AST_COLUMN_LIST, "<COLUMN_LIST>", NULL);

    Token token = getNextToken(sql, index, last_index);
    if ((token.type != TOKEN_STAR && token.type != TOKEN_IDENTIFIER)
                                || checkColref(token.value) != 0) {
        errMsg("ERROR: invalid column name: '%s'\n", token.value);
        destroyAST(column_list_node);
        return NULL;
    }

    if (token.type == TOKEN_STAR) {
        ASTNode *column_node = createASTNode(AST_STAR, "<STAR>", token.value);
        addChild(column_list_node, column_node);

        return column_list_node;
    }

    while (token.type == TOKEN_IDENTIFIER) {
        ASTNode *column_node = createASTNode(AST_COLUMN, "<COLUMN_NAME>", token.value);
        addChild(column_list_node, column_node);

        token = getNextToken(sql, index, last_index);
        if (token.type == TOKEN_COMMA) {
            token = getNextToken(sql, index, last_index);
        } else {
            break;
        }

        if (token.type != TOKEN_IDENTIFIER || checkColref(token.value) != 0) {
            *index = *last_index;   /* roll back */
            errMsg("ERROR: invalid column name: '%s'\n", token.value);
            destroyAST(column_list_node);
            return NULL;
        }
    }

    *index = *last_index;   /* roll back */
    return column_list_node;
}

PRIVATE ASTNode *parseTableList(const char *sql, int *index, int *last_index)
{
    ASTNode *table_list_node = createASTNode(AST_TABLE_LIST, "<TABLE_LIST>", NULL);

    Token token = getNextToken(sql, index, last_index);
    if (token.type != TOKEN_IDENTIFIER || checkTblref(token.value) != 0) {
        errMsg("ERROR: invalid table name: '%s'\n", token.value);
        destroyAST(table_list_node);
        return NULL;
    }

    while (token.type == TOKEN_IDENTIFIER) {
        ASTNode *table_node = createASTNode(AST_TABLE, "<TABLE_NAME>", token.value);
        addChild(table_list_node, table_node);

        token = getNextToken(sql, index, last_index);
        if (token.type == TOKEN_COMMA) {
            token = getNextToken(sql, index, last_index);
        } else {
            break;
        }

        if (token.type != TOKEN_IDENTIFIER || checkTblref(token.value) != 0) {
            *index = *last_index;   /* roll back */
            errMsg("ERROR: invalid table name: '%s'\n", token.value);
            destroyAST(table_list_node);
            return NULL;
        }
    }

    *index = *last_index;   /* roll back */
    return table_list_node;
}

PRIVATE ASTNode *parseCondition(const char *sql, int *index, int *last_index)
{
    ASTNode *condition_node = createASTNode(AST_CONDITION, "<CONDITION>", NULL);

    ASTNode *or_node = parseOr(sql, index, last_index);
    CHECK_NODE(or_node, condition_node);
    addChild(condition_node, or_node);

    return condition_node;
}

PRIVATE ASTNode *parseOr(const char *sql, int *index, int *last_index)
{
    ASTNode *or_node = createASTNode(AST_OR, "<OR>", NULL);

    ASTNode *and_node = parseAnd(sql, index, last_index);
    CHECK_NODE(and_node, or_node);
    addChild(or_node, and_node);

    Token token;
    while ((token = getNextToken(sql, index, last_index)).type == TOKEN_OR) {
        ASTNode *next_and_node = parseAnd(sql, index, last_index);
        CHECK_NODE(next_and_node, or_node);
        addChild(or_node, next_and_node);
    }
    *index = *last_index;

    return or_node;
}

PRIVATE ASTNode *parseAnd(const char *sql, int *index, int *last_index)
{
    ASTNode *and_node = createASTNode(AST_AND, "<AND>", NULL);

    ASTNode *expr_node = parseExpr(sql, index, last_index);
    CHECK_NODE(expr_node, and_node);
    addChild(and_node, expr_node);

    Token token;
    while ((token = getNextToken(sql, index, last_index)).type == TOKEN_AND) {
        ASTNode *next_expr_node = parseExpr(sql, index, last_index);
        CHECK_NODE(next_expr_node, and_node);
        addChild(and_node, next_expr_node);
    }
    *index = *last_index;

    return and_node;
}

PRIVATE ASTNode *parseExpr(const char *sql, int *index, int *last_index)
{
    ASTNode *expr_node = createASTNode(AST_EXPR, "<EXPR>", NULL);

    Token token = getNextToken(sql, index, last_index);
    if (token.type != TOKEN_IDENTIFIER || checkColref(token.value) != 0) {
        errMsg("ERROR: invalid column name: '%s'\n", token.value);
        destroyAST(expr_node);
        return NULL;
    }
    ASTNode *column_name_node = createASTNode(AST_COLUMN, "<COLUMN_NAME>", token.value);
    addChild(expr_node, column_name_node);

    token = getNextToken(sql, index, last_index);
    switch (token.type) {
        case TOKEN_GREATER:
        case TOKEN_LESS:
        case TOKEN_EQUAL:
        case TOKEN_ASSIGN:
        case TOKEN_GE:
        case TOKEN_LE:
        case TOKEN_NE:
            break;
        default:
            destroyAST(expr_node);
            errMsg("ERROR: invalid operator: '%s'\n", token.value);
            return NULL;
    }
    ASTNode *operator_node = createASTNode(AST_OPERATOR, "<OPERATOR>", token.value);
    addChild(expr_node, operator_node);

    token = getNextToken(sql, index, last_index);
    switch (token.type) {
        case TOKEN_STRING:
        case TOKEN_NUMBER:
            break;
        default:
            destroyAST(expr_node);
            errMsg("ERROR: invalid value: '%s'\n", token.value);
            return NULL;
    }
    ASTNode *value_node = createASTNode(AST_VALUE, "<VALUE>", token.value);
    addChild(expr_node, value_node);

    return expr_node;
}

PRIVATE ASTNode *parseStmtInsert(const char *sql, int *index, int *last_index)
{
    Token token;

    ASTNode *stmt_insert_node = createASTNode(AST_STMT_INSERT, "<STMT_INSERT>", NULL);

    ASTNode *insert_node = parseInsert(sql, index, last_index);
    CHECK_NODE(insert_node, stmt_insert_node);
    addChild(stmt_insert_node, insert_node);

    token = getNextToken(sql, index, last_index);
    if (token.type != TOKEN_INTO) {
        errMsg("ERROR: expected 'into'\n");
        destroyAST(stmt_insert_node);
        return NULL;
    }
    ASTNode *into_node = parseInto(sql, index, last_index);
    CHECK_NODE(into_node, stmt_insert_node);
    addChild(stmt_insert_node, into_node);

    token = getNextToken(sql, index, last_index);
    if (token.type != TOKEN_VALUES) {
        errMsg("ERROR: expected 'values'\n");
        destroyAST(stmt_insert_node);
        return NULL;
    }
    ASTNode *values_node = parseValues(sql, index, last_index);
    CHECK_NODE(values_node, stmt_insert_node);
    addChild(stmt_insert_node, values_node);

    return stmt_insert_node;
}

PRIVATE ASTNode *parseStmtDelete(const char *sql, int *index, int *last_index)
{
    Token token;

    ASTNode *stmt_delete_node = createASTNode(AST_STMT_DELETE, "<STMT_DELETE>", NULL);

    /* delete */
    ASTNode *delete_node = parseDelete(sql, index, last_index);
    CHECK_NODE(delete_node, stmt_delete_node);
    addChild(stmt_delete_node, delete_node);

    /* from */
    token = getNextToken(sql, index, last_index);
    if (token.type != TOKEN_FROM) {
        errMsg("ERROR: expected 'from'.\n");
        destroyAST(stmt_delete_node);
        return NULL;
    }
    ASTNode *from_node = parseFrom(sql, index, last_index);
    CHECK_NODE(from_node, stmt_delete_node);
    addChild(stmt_delete_node, from_node);

    /* join */
    token = getNextToken(sql, index, last_index);
    if (token.type != TOKEN_JOIN) {
        *index = *last_index;
    } else {
        ASTNode *join_node = parseJoin(sql, index, last_index);
        CHECK_NODE(join_node, stmt_delete_node);
        addChild(stmt_delete_node, join_node);
    }

    /* where */
    token = getNextToken(sql, index, last_index);
    if (token.type != TOKEN_WHERE) {
        *index = *last_index;
        return stmt_delete_node;
    } else {
        ASTNode *where_node = parseWhere(sql, index, last_index);
        CHECK_NODE(where_node, stmt_delete_node);
        addChild(stmt_delete_node, where_node);
    }

    return stmt_delete_node;
}

PRIVATE ASTNode *parseStmtUpdate(const char *sql, int *index, int *last_index)
{
    Token token;

    ASTNode *stmt_update_node = createASTNode(AST_STMT_UPDATE, "<STMT_UPDATE>", NULL);

    /* update */
    ASTNode *update_node = parseUpdate(sql, index, last_index);
    CHECK_NODE(update_node, stmt_update_node);
    addChild(stmt_update_node, update_node);

    /* set */
    token = getNextToken(sql, index, last_index);
    if (token.type != TOKEN_SET) {
        errMsg("ERROR: expected 'set'\n"); 
        destroyAST(stmt_update_node);
        return NULL;
    }
    ASTNode *set_node = parseSet(sql, index, last_index);
    CHECK_NODE(set_node, stmt_update_node);
    addChild(stmt_update_node, set_node);

    /* join */
    token = getNextToken(sql, index, last_index);
    if (token.type != TOKEN_JOIN) {
        *index = *last_index;
    } else {
        ASTNode *join_node = parseJoin(sql, index, last_index);
        CHECK_NODE(join_node, stmt_update_node);
        addChild(stmt_update_node, join_node);
    }

    /* where */
    token = getNextToken(sql, index, last_index);
    if (token.type != TOKEN_WHERE) {
        *index = *last_index;
        return stmt_update_node;
    } else {
        ASTNode *where_node = parseWhere(sql, index, last_index);
        CHECK_NODE(where_node, stmt_update_node);
        addChild(stmt_update_node, where_node);
    }

    return stmt_update_node;
}

PRIVATE ASTNode *parseInto(const char *sql, int *index, int *last_index)
{
    ASTNode *into_node = createASTNode(AST_CLAUSE_INTO, "<INTO>", "into");

    ASTNode *table_list_node = parseTableList(sql, index, last_index);    
    CHECK_NODE(table_list_node, into_node);
    addChild(into_node, table_list_node);

    return into_node;
}

PRIVATE ASTNode *parseValues(const char *sql, int *index, int *last_index)
{
    ASTNode *values_node = createASTNode(AST_CLAUSE_VALUES, "<VALUES>", "values");

    ASTNode *record_list_node = parseRecordList(sql, index, last_index);    
    CHECK_NODE(record_list_node, values_node);
    addChild(values_node, record_list_node);

    return values_node;
}

PRIVATE ASTNode *parseSet(const char *sql, int *index, int *last_index)
{
    ASTNode *set_node = createASTNode(AST_CLAUSE_SET, "<SET>", "set");

    ASTNode *exprs_node = parseExprs(sql, index, last_index);
    CHECK_NODE(exprs_node, set_node);
    addChild(set_node, exprs_node);

    return set_node;
}

PRIVATE ASTNode *parseDelete()
{
    ASTNode *delete_node = createASTNode(AST_CLAUSE_DELETE, "<DELETE>", "delete");

    return delete_node;
}

PRIVATE ASTNode *parseInsert()
{
    ASTNode *insert_node = createASTNode(AST_CLAUSE_INSERT, "<INSERT>", "insert");

    return insert_node;
}

PRIVATE ASTNode *parseUpdate(const char *sql, int *index, int *last_index)
{
    ASTNode *update_node = createASTNode(AST_CLAUSE_UPDATE, "<UPDATE>", "update");

    ASTNode *table_list_node = parseTableList(sql, index, last_index);
    CHECK_NODE(table_list_node, update_node);
    addChild(update_node, table_list_node);

    return update_node;
}

PRIVATE ASTNode *parseRecordList(const char *sql, int *index, int *last_index)
{
    ASTNode *record_node;
    ASTNode *record_list_node = createASTNode(AST_RECORD_LIST, "<RECORD_LIST>", NULL);

    record_node = parseRecord(sql, index, last_index);
    CHECK_NODE(record_node, record_list_node); 
    addChild(record_list_node, record_node);

    Token token;
    while ((token = getNextToken(sql, index, last_index)).type == TOKEN_COMMA) {
        record_node = parseRecord(sql, index, last_index);
        CHECK_NODE(record_node, record_list_node); 
        addChild(record_list_node, record_node);
    }

    *index = *last_index;   /* roll back */
    return record_list_node;
}

PRIVATE ASTNode *parseRecord(const char *sql, int *index, int *last_index)
{
    Token token;
    int pos = 0;
    ASTNode *record_node = createASTNode(AST_RECORD, "<RECORD>", NULL);

    token = getNextToken(sql, index, last_index);
    if (token.type != TOKEN_LP) {
        errMsg("ERROR: expected '('\n");
        return NULL;
    }
    strcpy(record_node->value + pos, token.value);
    pos += strlen(token.value);

    while ((token = getNextToken(sql, index, last_index)).type != TOKEN_RP) {
        strcpy(record_node->value + pos, token.value);
        if (pos + strlen(token.value) > MAX_VALUE_LEN) {
            errMsg("ERROR: lack of ')'\n");
            destroyAST(record_node);
            return NULL;
        }
        pos += strlen(token.value);
    }

    strcpy(record_node->value + pos, token.value);
    pos += strlen(token.value);
    record_node->value[pos] = '\0';

    return record_node;
}

PRIVATE ASTNode *parseExprs(const char *sql, int *index, int *last_index)
{
    ASTNode *expr_node;
    ASTNode *expr_list_node = createASTNode(AST_EXPR_LIST, "<EXPR_LIST>", NULL);

    expr_node = parseExpr(sql, index, last_index);
    CHECK_NODE(expr_node, expr_list_node);
    addChild(expr_list_node, expr_node);

    Token token;
    while ((token = getNextToken(sql, index, last_index)).type == TOKEN_COMMA) {
        expr_node = parseExpr(sql, index, last_index);
        CHECK_NODE(expr_node, expr_list_node);
        addChild(expr_list_node, expr_node);
    }

    *index = *last_index;   /* roll back */
    return expr_list_node;
}

PRIVATE int checkColref(const char *ref)
{
    for (size_t i = 0; i < (size_t) sizeof(colrefs) / sizeof(colrefs[0]); i++) {
        if (strcmp(ref, colrefs[i]) == 0)
            return 0;
    }
    return -1;
}

PRIVATE int checkTblref(const char *ref)
{
    for (size_t i = 0; i < (size_t) sizeof(tblrefs) / sizeof(tblrefs[0]); i++) {
        if (strcmp(ref, tblrefs[i]) == 0)
            return 0;
    }
    return -1;
}

PRIVATE ASTNode *parseJoin(const char *sql, int *index, int *last_index)
{
    ASTNode *join_node = createASTNode(AST_CLAUSE_JOIN, "<JOIN>", "join");

    ASTNode *table_list_node = parseTableList(sql, index, last_index);
    CHECK_NODE(table_list_node, join_node);
    addChild(join_node, table_list_node);

    return join_node;
}

/* PRIVATE function implemention end */